#include<iostream>

using namespace std;
 struct Node {
     int val;
      struct Node *next;
      struct Node *random;
 };
 
typedef struct Node Node;

struct Node* copyRandomList(struct Node* head)
{
    Node* cur = head;
    while (cur)
    {
        Node* copy = (Node*)malloc(sizeof(Node));
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
        cur = copy->next;
    }
    cur = head;
    while (cur)
    {
        Node* copy = cur->next;
        if (cur->random == NULL)
        {
            copy->random = NULL;
            cur = copy->next;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }
    Node* phead, * ptail;
    phead = ptail = NULL;
    cur = head;
    while (cur)
    {
        Node* copy = cur->next;
        Node* next = copy->next;
        if (ptail == NULL)
        {
            phead = ptail = copy;
        }
        else
        {
            ptail->next = copy;
            ptail = ptail->next;
        }
        cur->next = next;
        cur = next;

    }
    return phead;
}

int main()
{

    return 0;
}
